Skip to main content

谈谈 React diff 算法

是什么​

DOM diff 就是对比两颗虚拟 DOM 树的算法。当组件变化时，会 render 出一个新的虚拟 DOM，diff 算法对比新旧虚拟 DOM 之后，得到一个 patch 状态数组,然后 React 用 patch 状态数组 来更新真实 DOM

树 diff 的时间复杂度 O(n3)​

首先，遍历 tree1；其次，遍历 tree2；最后，对树进行排序。这样 nnn ，就达到了 O(n3)。

优化时间复杂度到 O(n)​

通过 diff 算法，我们可以将时间复杂度从 O(n3)优化到 O(n):

怎么做（diff 策略）​

  1. tree diff

    React 会对树进行分层比较，两棵树只会对同一层次的节点进行比较。

  2. component diff

    拥有相同类型的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。

    React 会先判断是否是同一类型的组件，不是就不会比较二者的结构，直接删除，重新创建。

  3. element diff

    对于同一层级的一组子节点，它们可以通过唯一 key 进行区分。

    开发者对同一层级的子节点，可以添加唯一索引进行区分，这样在 diff 时，涉及到只是位置变化的，可以只移动元素，避免删除创建等重复的操作。

    递归新虚拟 dom 树子节点 遍历查找 旧虚拟 dom 树子节点,进行状态判断 存入 patch 状态数组，统一处理 patch 状态数组

原理​

源码：手写 reac-dom-diff

参考文章​